package com.person.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 22.括号生成
 * 2022-06-13 17:19:00
 **/
public class Sequence_0022_GenerateParentheses {
    public static void main(String[] args) {
        Solution solution = new Sequence_0022_GenerateParentheses().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
//    若干年之后来看,还是觉得自己傻逼
//    class Solution {
//        private static final String[] arr = {"(", ")"};
//        private Stack<Integer> stack = new Stack<>();
//        private int[] count = {0, 0};
//
//        //所有 回溯 递归
//        //晕死,定义的栈无语死了
//        public List<String> generateParenthesisMy(int n) {
//            List<String> ans = new ArrayList<>();
//            List<String> res = new ArrayList<>();
//            generate(ans, "", 2 * n, n, n);
//            for (int i = 0; i < ans.size(); i++) {
//                String s = ans.get(i);
//                Stack<Character> stack = new Stack<>();
//                int j = 0;
//                for (j = 0; j < s.length(); j++) {
//                    char c = s.charAt(j);
//                    if ('{' == c) {
//                        stack.push('{');
//                    } else {
//                        if (!stack.isEmpty()) {
//                            Character pop = stack.pop();
//                            if (pop != null && pop == '{') {
//
//                            } else {
//                                break;
//                            }
//                        } else {
//                            break;
//                        }
//                    }
//                }
//                if (stack.isEmpty() && j == s.length() - 1) {
//                    res.add(s);
//                }
//            }
//            return res;
//        }
//
//        private void generate(List<String> ans, String sb, int n, int pre, int suf) {
//            if (n < 1) {
//                ans.add(sb);
//            } else {
//                for (int i = 0; i < 2; i++) {
//                    if (i == 0) {
//                        if (pre > 0) {
//                            generate(ans, sb + arr[i], n - 1, pre - 1, suf);
//                        }
//                    } else {
//                        if (suf > 0) {
//                            generate(ans, sb + arr[i], n - 1, pre, suf - 1);
//                        }
//                    }
//                }
//            }
//        }
//    }

    class Solution {
        //暴力破解 深度遍历
        public List<String> generateParenthesis(int n) {
            List<String> combinations = new ArrayList<String>();
            generateAll(new char[2 * n], 0, combinations);
            return combinations;
        }

        public void generateAll(char[] current, int pos, List<String> result) {
            if (pos == current.length) {
                if (valid(current)) {
                    result.add(new String(current));
                }
            } else {
                current[pos] = '(';
                generateAll(current, pos + 1, result);
                current[pos] = ')';
                generateAll(current, pos + 1, result);
            }
        }

        public boolean valid(char[] current) {
            int balance = 0;
            for (char c: current) {
                if (c == '(') {
                    ++balance;
                } else {
                    --balance;
                }
                if (balance < 0) {
                    return false;
                }
            }
            return balance == 0;
        }
    }


//leetcode submit region end(Prohibit modification and deletion)

}